Hola GerTorresM
Los archivos de implementación e Interfaz son los que generan el código para poder importar el WSDL, de hecho en el archivo de interfaz es donde publicas las clases y métodos que serán "mostrados" en el WSDL y el archivo de implemenmtación (como su nombre lo indica) es el que contine la lógica de negocios de los métodos publicados en el archivo de interfáz.
Te recomiendo vuelvas a crear tu Servicio Web y dile que sí te agregue esos archivos.
Puedes seguir
éste tutorial, aunque muy, muy, básico, te dará una idea de lo que estás intentando hacer.
Saludos