El castillo ocupa la Peña Feliciana, el punto con mejor visibilidad de la loma donde se encarama Sos. Su estructura, como señala Guitart, es la habitual en los castillos altoaragoneses de los siglos X al XII. Consta de un recinto amurallado de trazado irregular, con una esbelta torre en su centro y un torreón cilíndrico con dos hileras de ventanas saeteras en su ángulo noroccidental. Un conjunto que se remataba con la ubicación de la Iglesia de San Esteban, a los pies del alto del castillo. Además, en una sobreelevación más al Sur debió de existir otra fortificación hoy desaparecida que ocuparía el solar sobre el que se levanta el Palacio de los Sada. El castillo, cuyos vestigios todavía pueden contemplarse en la actualidad, no es, sin embargo, el primigenio, ya que en ese punto hubo una construcción anterior, en el siglo x, con que los monarcas pamploneses hacían frente a la frontera musulmana. Fue edificado por Sancho Garcés II de Navarra en el año 970 y, como señala Cabañero Subiza, hay testimonios de la asunción de la piedra en su construcción al menos desde el año 975. Sería reforzado por Sancho Garcés III el Mayor en el 1012. Además, diversas campañas arqueológicas han permitido sacar a la luz la planta de la fortaleza de los años centrales del reinado de Ramiro I (1035-1064) que contaría con una organización distinta a la actual. Seguiría modelos de distribución islámicos, con una planta rectangular con al menos dos torres en el muro norte. De aquel conjunto ha quedado testimonio, además, de la existencia de un patio de armas parcialmente cubierto, amén de añadidos bajomedievales, como hornos para la fundición de metales y un sistema de canalización. La torre que hoy se puede contemplar, no obstante, ha sido clasificada como perteneciente a una época posterior, construida a instancias de Ramiro II el Monje (1134-1137) entre 1134 y 1137 por el Maestro Jordán. Hemos de advertir que gran parte de su aspecto actual se debe a la restauración llevada a cabo por el arquitecto Emilio Larrodera entre 1941 y 1944. Fue erigida en piedra sillar, con unas hiladas que oscilan entre los 28 cm de la hilada menor y los 52 cm de la mayor. Se asienta sobre la roca madre y presenta una planta cuadrada, de 6 m de lado. Pese a su aparente solidez exterior, el actual mal estado de su estructura interna desaconseja su acceso. El último cuerpo posee en cada uno de sus paños una ventana centrada, en arco de medio punto y cegada. Este remate se completa con una hilera de almenas que fueron añadidas en la citada restauración, aunque siguiendo las que había con anterioridad. Asimismo, posee dos puertas de entrada, en los lados norte y sur. La puerta septentrional está cegada, mientras que la meridional vio sus arcos de medio punto modificados con la adición de sillares irregulares, de modo que el acceso ahora es adintelado. Especial atención merece la curiosa solución del despiece del arco inferior, puesto que sus dovelas son irregulares y presentan un ángulo de despiece igualmente irregular. A propósito de esto, conviene comentar la existencia de soluciones similares en, al menos, dos localidades navarras. Se trata de las iglesias de San Juan Bautista de Eristain, en la Valdorba, cerca de Tafalla, y San Miguel de Villatuerta, junto a Estella. Uranga e Íñiguez las engloban en un grupo anterior al románico pleno, con elementos diversos de la arquitectura musulmana, asturiana y carolingia (una inscripción proporciona para Villatuerta datación firme a finales del siglo x). Vemos en ellas las dovelas largas y delgadas, que algunos autores consideran propias de usos constructivos islámicos y que también reconocemos en Sos. Según Uranga e Íñiguez en los dos templos navarros se habían rapado las piedras salmeres para modernizar las puertas en arco de herradura y transformarlas en arco de medio punto. Entienden que en la de Eristain reaprovecharon materiales anteriores, mezclando dovelas grandes con otras más finas y dando como resultado un efecto de cuña irregular. Las dovelas no seguían radialmente el centro del arco, al igual que ocurre en Sos.