Within the main (Disney) canon of Star Wars, Han Solo's captaincy in A New Hope was in recognition of being master of his own vessel, the Millennium Falcon, noting that we learn in Solo that his highest military rank (prior to his desertion from the Imperial Fleet) was that of Lieutenant.
"Han Solo. I'm captain of the Millennium Falcon." - Star Wars : A New Hope.
In the George Lucas novelisation of A New Hope, Chewbacca describes Solo to Ben Kenobi as the ship's "captain-owner", again confirming that the intention is that he's the master of his own vessel, rather than being a military-ranked captain.
“This is Chewbacca,” he explained when the anthropoid had joined them at the bar. “He’s first mate on a ship that might suit our needs. He’ll take us to her captain-owner now.”
Interestingly, it would appear that Solo was actually made a captain in the Rebellion Fleet at some point after the Battle of Yavin, prior to his elevation to General, so he becomes a bona-fide captain at some point between A New Hope and The Empire Strikes Back.
After the victory at Yavin, Han eventually accepts a commission as captain in the Rebel Alliance. At frozen Echo Base he volunteers for difficult perimeter patrol duty even though he doesn't like tauntauns or the cold. Han is a natural leader and serves as an inspiration to many of the troopers around him.
Star Wars: The Complete Visual Dictionary (New Edition)
This mildly conflicts with what we seen in Star Wars (2015) #55 where he's made a colonel in the Rebel Alliance, but claims that he doesn't have any intention of taking a rank. Possibly he just means a leadership rank.

Moving down into the EU novels, The Hutt Gambit deals with Han Solo's earlier life. In it we learn that although Solo did undertake military service in the Imperial Army, his highest rank was that of Lieutenant.
Han Solo, former Imperial officer, sat despondently at a sticky table in a dingy bar on Devaron, sipping an inferior Alderaanian ale and wishing he were alone.
The huge, hairy being gazed back at him with concerned blue eyes. Han sighed heavily. If only he’d go home— But the Wookiee — Chew-something — utterly refused to go home to Kashyyyk, despite Han’s repeated urging. The alien claimed he owed something called a “life debt” to former Imperial Lieutenant Han Solo.
In ESB, he was evidently appointed to the rank of General in the Rebel Alliance. Note also that Lando (previously City Administrator (and owner) of a small mining facility) is also appointed General at the same time.