Advanced melanoma cells, characterized by resistance to chemotherapy, have been shown to be highly sensitive to oncolysis by Newcastle disease virus (NDV). In the present study, we investigated the capacity of NDV to specifically infect and spread into solid tissues of human melanoma and lung carcinoma, in vivo and ex vivo. For this purpose a new model of SCID-beige mice implanted with human melanoma was developed. Surprisingly, the replication competent NDV-MTH and the attenuated, single-cycle replication NDV-HUJ strains, demonstrated a similar oncolytic activity in the melanoma-implanted mice. Further, ex vivo analysis, using organ cultures derived from the melanoma tissues indicated a limited spread of the two NDV strains in the tissue. Extracellular matrix (ECM) molecules, notably heparin sulfate and collagen, were found to limit viral spread in the tissue. This observation was validated with yet another solid tumour of human lung carcinoma. Taken together, the results indicate that the ECM acts as a barrier to virus spread within solid tumour tissues and that this restriction must be overcome to achieve effective oncolysis with NDV.