Sachverhalt: A. Das Strafgericht des Kantons Basel-Stadt sprach X._ am 8. November 2002 der Hehlerei, der Urkundenfälschung, der mehrfachen qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz sowie der Widerhandlung gegen das Waffengesetz schuldig und verurteilte ihn zu einer zweijährigen Gefängnisstrafe und zu einer Busse von Fr. 500.--. Von der Anklage der vorsätzlichen Tötung sprach es X._ frei. Auf Appellation von X._ hin bestätigte das Appellationsgericht des Kantons Basel-Stadt am 24. März 2004 das erstinstanzliche Urteil. B. X._ erhebt eidgenössische Nichtigkeitsbeschwerde beim Bundesgericht mit dem Antrag, der angefochtene Entscheid sei aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. C. Sowohl das Appellationsgericht als auch die Staatsanwaltschaft des Kantons Basel-Stadt ersuchen um Abweisung der Beschwerde. D. Der Präsident des Kassationshofs hat der Beschwerde mit Verfügung vom 1. September 2004 die aufschiebende Wirkung erteilt.