The nickname GOP can be dated back to at least 1875 (21 years after the party's founding), when the phrase "Grand Old Party" was first used in newspapers. In the 1880s, British Prime Minister William Gladstone was routinely referred to as GOM, or "Grand Old Man," by the British press, and the Republicans believe this may have further stimulated the widespread use of GOP in America.
It is interesting to note that the modern Republican Party, founded in 1854, is actually younger than the modern Democratic Party (founded in 1832).