This paper develops a theory for completely random measures in the framework of free probability. A general existence result for free completely random measures is established, and in analogy to the classical work of Kingman it is proved that such random measures can be decomposed into the sum of a purely atomic part and a (freely) infinitely divisible part. The latter part (termed a free Lévy basis) is studied in detail in terms of the free Lévy-Khintchine representation and a theory parallel to the classical work of Rajput and Rosiński is developed. Finally a Lévy-Itô type decomposition for general free Lévy bases is established.