Note: this answer was written before the re-canonising of Star Wars by Disney and the release of the Solo movie
Apparently, Solo was kicked out of the Imperial Academy (from Wookieepedia)
Solo then entered the Imperial Academy at Carida, serving with distinction. He was kicked out, however, when he stopped an Imperial officer from beating a Wookiee named Chewbacca with a neuronic whip for resisting capture.
He spent a few years being a smuggler (which he had been before entering the academy) before being hired for what seemed to be an easy passenger flight from TattooineTatooine to Alderaan. The rest, as they say, is history.