With 5 minutes remaining in the first half, Darren Mackie had a shot cleared off the line keeping the sides level at the break.
It was all Aberdeen in the early stages of the second half and they got their reward when in the 57th minute Ricky GILLIES dived to head a Derek Young cross past the helpless McCaldon.
The Dons continued to attack the Livingston defence, and Nigel Pepper was unlucky when his blistering strike was well saved by McCaldon. Michael Hart, Eoin Jess and Ilian Kiriakov were all introduced in the closing stages, and the visitors were unable to force the game in extra-time, giving Ebbe Skovdahl his first win as Aberdeen Manager.