The island and community has undergone numerous name changes. It was originally Penobscot Island, part of the Waldo Patent. When Henry Knox bequeathed it to his orphaned grandchildren, it became known as Orphan Island. In 1839 it became the plantation of Wetmore Isle. The name was changed to Verona (after Verona, Italy) upon its incorporation as a town on February 18, 1861. The town lengthened its name to Verona Island, matching the name of the landform on which it was located, in a March 27, 2004 referendum.
The island was once a shipbuilding village. In 1905 the last vessel was built. This was the Roosevelt, which carried Robert Peary from New York to the Arctic in 1908 for his final expedition to the North Pole.
The Waldo–Hancock Bridge (carrying U.S. 1), which opened November 16, 1931 to connect Verona Island and Prospect in Waldo County, is on the National Register of Historic Places but was in such bad condition that it was replaced. Demolition of the bridge is set to begin on October 1, 2012.
The new bridge, opened on December 30, 2006, is called the Penobscot Narrows Bridge and Observatory. The legislature's Transportation Committee originally decided it would be named the Downeast Gateway Bridge, but strong opposition by community leaders from eastern Waldo County forced this decision to be reconsidered. The new name was unanimously approved on March 9, 2006 by the legislature's Transportation Committee.