Sufficient conditions are established for the completeness of (world) labelled first-order based logics. These conditions are shown to be preserved by fibring, leading to the preservation of completeness. A comparison with non-labeled approaches is outlined. Some examples are given involving modal and relevance logics.