Erlang was born at Lønborg, near Tarm, in Jutland. He was the son of a schoolmaster, and a descendant of Thomas Fincke on his mother's side. At age 14, he passed the Preliminary Examination of the University of Copenhagen with distinction, after receiving dispensation to take it because he was younger than the usual minimum age. For the next two years he taught alongside his father.

A distant relative provided free board and lodging, and Erlang prepared for and took the University of Copenhagenentrance examination in 1896, and passed with distinction. He won a scholarship to the University and majored inmathematics, and also studied astronomy, physics and chemistry. He graduated in 1901 with an MA and over the next 7 years taught at several schools. He maintained his interest in mathematics, and received an award for a paper that he submitted to the University of Copenhagen.

He was a member of the Danish Mathematicians' Association (TBMI) and through this met amateur mathematician Johan Jensen, the Chief Engineer of theCopenhagen Telephone Company (KTAS in Danish), an offshoot of the International Bell Telephone Company. Erlang worked for the CTC (KTAS) from 1908 for almost 20 years, until his death in Copenhagen after an abdominal operation.

He was an associate of the British Institution of Electrical Engineers.