Am 7. November 1866 kaum Paul Lincke in Berlin zur Welt und verbrachte dort seine Jugendjahre. Sein Vater, ein Beamter des Berliner Magistrats, starb früh an Cholera. Schon im Kindesalter zeigte sich Linckes besondere Vorliebe für die Musik, insbesondere für die Militärmusik. Statt in den Schulunterricht, zog es ihn oft zur Wachablösung unter den Linden. Im Jahr 1880 erkannte seine Mutter das musikalische Talent ihres Sohnes und förderte ihn. Sie schickte ihn zur Ausbildung an die „Stadtpfeiferei“ nach Wittenberge. Dank seiner Begabung und seines Fleisses durfte der junge Lincke bald kleinere Aufgaben bei Konzertaufführungen übernehmen. Nach vier Jahren schloss er seine Ausbildung ab und präsentierte seine erste Komposition, den Marsch „Gruss an Wittenberge“.
Zurück in Berlin bewarb sich Lincke bei mehreren Militärkapellen. Obwohl er die eigentliche Aufnahmeprüfung fürdie preussische Armee mit Bravour bestand, wurde ihm von den Militärärzten der Eintritt aufgrund seines zu geringen Brustumfangs verwehrt. Stattdessen fand er eine Anstellung als Fagottist am Central-Theater, wechselte jedoch 1885 ans Ostend-Theater. 1887 trat er für drei Jahre am Königstädtischen Theater am Alexanderplatz auf. Im Frühjahr 1893 dirigierte Lincke eines der traditionellen Berliner Pfingstkonzerte im Garten des Belle-Alliance-Theaters.
Am Königstädtischen Theater traf Lincke auf den Schauspieler Heinz Bolten aus Chemnitz, der fortan eine prägende Rolle in seiner beruflichen Laufbahn spielte. 1897 feierte Lincke mit seinem Einakter „Venus auf Erden“ einen grossen Erfolg. Paul Lincke verstarb am 3. September 1946 in Clausthal-Zellerfeld, wohin er sich während des Krieges zurückgezogen hatte.
Lincke widmete sich zeitlebens der leichten Musik. Aus seiner Feder stammen zahlreiche Possen, Lieder und mehrere Bühnenwerke. Besonders hervorzuheben ist seine Operette „Frau Luna„, die bis heute grosse Bekanntheit geniesst. Lincke verstand es, eingängige Melodien zu komponieren, die im Gedächtnis bleiben. Stücke wie „Schlösser, die im Monde liegen“, das „Glühwürmchen-Idyll“, „Folies Bergère“ oder das „Geburtstagsständchen“ sind noch immer beliebte Ohrwürmer. Sein bekanntestes Werk jedoch bleibt der Marsch „Berliner Luft“, der – ähnlich wie der Donauwalzer in Wien – oft als inoffizielle Hymne Berlins bezeichnet wird. Viele seiner Stücke klingen durch ihre beschwingten Walzerpassagen fast wienerisch, insbesondere in Frau Luna. Lincke, oft als „Johann Strauss Deutschlands“ bezeichnet, schuf mit der Berliner Operette das Pendant zur Wiener Operette.