Ende 2005 lernen sich in Münster der Gitarrist Florian Füntmann, Bassist Jan Hoffmann und Schagzeuger Janosch Rathmer kennen. In der Besetzung kommen erste Jams zustande, und nach einer Weile stößt als weiterer Gitarrist David Jordan dazu, und die Band ist geboren. Rathmer und Füntmann kommen vom Melodic Death Metal, und auch die anderen Bandmitglieder haben bereits musikalische Vorerfahrung. Für den Bandnamen entscheidet man sich aufgrund des Zusammenklangs der Wörter. Da die Band keinen Sänger findet, arbeitet sie erst einmal instrumental. Ihr Debüt-Demo "DMNSTRTN" wird direkt zum Demo des Monats – sowohl bei Visions als auch beim Rock Hard Magazin.
Es folgen zahlreiche Konzerte, erste Alben und Touren im Vorprogramm von Bands wie Opeth, Katatonia oder Dredg. Long Distance Calling gelten als exzellente Liveband und kreieren lange, epische Songs, deren Fokus auf Rhythmus, Wiederholung und einer gewissen Härte liegen.