The word "Colombia" comes from Christopher Columbus name, and was conceived by the revolutionary Francisco de Miranda as a reference to the New World, specially to all american territories and colonies under spanish and portuguese rule.
Bolivar and other revolutionaries in the First Republic of Venezuela used this name for all Spanish America, until the republic under that name was founded in 1819 at the Congress of Angostura. It was conceived initialy in that Congress as a federal republic, made up of three departments with capitals in the cities of Bogotá (Department of Cundinamarca), Caracas (Department of Venezuela), and Quito (Department of Quito). In that year, not all provinces of the former viceroyalty were yet free.
The Constitution of the new republic was given in 1821 in the Congress of Cucuta, establishing it's capital in Bogota. A new territorial division (various departaments corresponding to Venezuela, New Granada and Quito) was conceived. The famous general Simon Bolivar was elected president and Francisco de Paula Santander vicepresident. In the first years of existence, Gran Colombia helped other provinces still in war with Spain to become independent, so Panama came to the federation in 1821 and so did the remaining provinces corresponding to Quito and to Venezuela. The independence of Peru was consolidated through Gran Colombia's aid. Bolivar and Santander were reelected in 1826. Permanent changes of the political division during the existence of Gran Colombia, with local confrontations between the regions, showed the instability of the estate.
Bolívar dreamt of uniting South America but was unable to achieve this during the struggle for independence. The Republic of Gran Colombia was Bolívar's initial attempt of creating one single South American state. Other South American polititians objected to his idea and Bolívar, disgruntled, resigned in 1828.
The federation was dissolved in 1830, despite the efforts of general Rafael Urdaneta in Bogota, due to internal strife between the different regions which strengthened after Bolívar's resignation.
The dissolution of Gran Colombia characterized the failure of Bolívar's dream.
In 1863, one of the new countries which remained after the dissolution, New Granada, changed its name officially to "United States of Colombia", and in 1886 adopted its present day name: "Republic of Colombia". Panama remained as a province of this country until 1903, when it became independent, sponsored by the U.S.
Another federal state on the American continent that underwent a similar fate was the United States of Central America.