Kleinrock's best-known and significant work is his early work on queueing theory, which has applications in many fields, among them as a key mathematical background to packet switching, one of the basic technologies of the Internet. His initial contribution to this field was his doctoral thesis at the Massachusetts Institute of Technology in 1962, published in book form in 1964; he later published several of the standard works on the subject. He described this work as:

"Basically, what I did for my PhD research in 1961–1962 was to establish a mathematical theory of packet networks..."

The first message on the ARPANET was sent by UCLA student programmer Charley Kline, at 10:30 p.m, on October 29, 1969 from Boelter Hall 3420, the school's main building.[10] Supervised by Kleinrock, Kline transmitted from the university's SDS Sigma 7 host computer to the Stanford Research Institute's SDS 940 host computer. The message text was the word "login"; the "l" and the "o" letters were transmitted, but the system then crashed. Hence, the literal first message over the ARPANET was "lo". About an hour later, having recovered from the crash, the SDS Sigma 7 computer effected a full "login". The first permanent ARPANET link was established on November 21, 1969, between the IMP at UCLA and the IMP at the Stanford Research Institute. By December 5, 1969, the entire four-node network was established.[11][12]

Room 3420 at Boelter Hall was restored to its condition of 1969 and converted into the Kleinrock Internet Heritage Site and Archive. It opened to the public with a grand opening attended by Internet pioneers on October 29, 2011.[10][17] Kleinrock claims to have committed the first illegal act on the Internet, having sent a request for return of his electric razor after a meeting in England in 1973. At the time, use of the Internet for personal reasons was unlawful.[18]

He has received numerous professional awards. Kleinrock was selected to receive the prestigious National Medal of Science, the nation's highest scientific honor, from President George W Bush in the White House on September 29, 2008. "The 2007 National Medal of Science to Leonard Kleinrock for his fundamental contributions to the mathematical theory of modern data networks, and for the functional specification of packet switching, which is the foundation of Internet technology. His mentoring of generations of students has led to the commercialization of technologies that have transformed the world."[2] In 2010 he shared the Dan David Prize.[19] In 2012, Kleinrock was inducted into the Internet Hall of Fame by the Internet Society.[20] Leonard Kleinrock was inducted into IEEE-Eta Kappa Nu (IEEE-HKN) in 2011 as an Eminent Member. The designation of Eminent Member is the organization's highest membership grade and is conferred upon those select few whose outstanding technical attainments and contributions through leadership in the fields of electrical and computer engineering have significantly benefited society. In September 2014, Leonard Kleinrock was awarded the ACM SIGMOBILE Outstanding Contribution Award at MobiCom 2014.

^Still, tapping into the ARPANET to fetch a shaver across international lines was a bit like being a stowaway on an aircraft carrier. The ARPANET was an official federal research facility, after all, and not something to be toyed with. Kleinrock had the feeling that the stunt he’d pulled was slightly out of bounds. 'It was a thrill. I felt I was stretching the Net'. - "Where Wizards Stay Up Late: The Origins of the Internet", Chapter 7.

Kleinrock discusses his dissertation work in queuing theory, and his move to the University of California at Los Angeles (UCLA). As one of the main contractors for the ARPANET, Kleinrock describes his involvement in discussions before the official DARPA request was issued, the people involved in the ARPANET work at UCLA, the installation of the first node of the network, the Network Measurement Center, and his relationships with Lawrence Roberts and the IPT Office, Bolt, Beranek and Newman, and the Network Analysis Corporation.