El rey tenía que agradecer su retorno al trono de León sobre todo a la energía y a los buenos consejos de su hermana Urraca. En lo sucesivo, el influjo de ésta sobre su hermano se hizo cada vez mayor. Don Alfonso no hacía nada sin su aprobación; le pedía que diera el visto bueno a cada uno de sus decretos. La relación entre ambos era tan íntima, que la gente sospechaba que llegaban hasta el incesto. Y estos rumores habían llegado a Andalucía. Cuando las habladurías adquirieron un cariz peligroso, sumándose a ellas el hecho de que la intimidad entre ambos hermanos parecía confirmar la participación del rey en el asesinato perpetrado en Zamora, don Alfonso empezó a actuar. Era un rey dulce y complaciente, y daba la impresión de ser un hombre fácilmente manejable, pero en realidad era más tenaz y perseverante de lo que la mayoría de la gente suponía. Sólo, que perseguía sus metas con infinita paciencia.
A principios del verano del año 1074, año y medio después de ayudarlo doña Urraca a recuperar el trono, don Alfonso aprovechó la llegada de su prometida, Agnes de Aquitania, para devolver a su hermana al convento, cuya administración le había dejado en herencia su padre. Acto seguido, se reconcilió con los nobles castellanos, dándoles un cierto grado de autonomía y nombrando al más poderoso de ellos, el conde Gonzalo Salvadórez, administrador de la porción castellana del reino. Al mismo tiempo, se dedicó con tenaz celo a restringir el poder de las familias de la nobleza y a recortar la independencia soberana de los obispos y abades, para lo cual se sirvió de refuerzos foráneos. Obligó a los señores de la Iglesia a introducir en la misa el rito único prescrito por Roma, y a reconocer de esta manera el primado del Papa, con lo que don Alfonso se ganó las simpatías de éste. Aumentó la suma que ya su padre había pagado al monasterio francés de Cluny a mil meticales al año, y más adelante incluso a dos mil, con lo cual no sólo compró una misa diaria para su padre y una segunda para él, en las que los monjes mencionaban sus nombres y hacían caer sobre ellos las bendiciones del Señor -lo que contribuía a aumentar su prestigio internacional-, sino que además, y sobre todo, se ganó el apoyo de este monasterio reformista, el más poderoso de la cristiandad occidental. Subordinó varios monasterios españoles al de Cluny, librándolos así de la influencia de los nobles y obispos, y sometiendo a los monjes procedentes de la nobleza a la disciplina caustral cluniacense, que les prohibía inmiscuirse demasiado en cuestiones políticas. Al mismo tiempo, trajo cada vez más franceses a su país, lo mismo hijos de campesinos que hijos de condes, aventureros, caballeros sin heredad deseosos de adquirir un feudo luchando contra los sarracenos, monjes y sacerdotes eruditos que eran nombrados obispos o abades, o llevados a la corte de León como asesores. Los franceses llegaron en tal cantidad que pronto no hubo prácticamente ninguna ciudad española que no tuviera su propio barrio franco.
La política matrimonial del rey también apuntaba hacia Francia. Su primer matrimonio tuvo un desdichado desenlace. Agnes de Aquitania tenía catorce años cuando llegó a León; don Alfonso contaba entonces treinta y uno. El rey no había podido llegar a nada con su jovencísima esposa, por lo cual mantenía una concubina, que le dio dos hijas: Elvira y Teresa. La joven reina murió cuatro años después de su llegada, inadvertida y olvidada.
El segundo matrimonio fue más afortunado. Se realizó por mediación del abad Hugo de Cluny, uno de los hombres más influyentes de la Europa de entonces. El abad pertenecía a la familia de los duques de Borgoña, y de ahí provenía también la nueva prometida del rey: una sobrina del abad, Constance de Borgoña, hija del duque Roberto de Borgoña y nieta del rey francés Roberto el Piadoso.
Constance llegó a León a principios del año 1079, acompañada de todo un enjambre de compatriotas, entre los que se encontraban dos de sus sobrinos, que más tarde harían carrera en España: Raymond de Borgoña y Henri de Borgoña.
Ese mismo año, don Alfonso se atribuyó por primera vez el título de emperador y elevó sus pretensiones sobre el dominio de toda la península. Imperator totius Hispaniae lo llamarían en adelante los monjes de Cluny en sus plegarias.
Tres años antes don Alfonso ya había intentado ensanchar su reino. El rey de Navarra había sido asesinado por su hermano menor. Los nobles del país habían desterrado al asesino y dividido el reino. El este, con la capital, Pamplona, había correspondido al rey de Aragón; el oeste, con la fértil Rioja, a don Alfonso. Desde entonces, además del condado de Barcelona, sólo había dos reinos españoles en el norte: Aragón y León. Don Alfonso podía dirigir todas sus fuerzas contra los principados moros que se extendían más allá de sus fronteras. El primer objetivo que se fijó fue la antigua capital, Toledo. Y para conseguirla ni siquiera tuvo que entablar batalla: se le ofreció casi sin que tuviera que intervenir.
En el año 1075, poco después de que Ibn Ukasha conquistara Córdoba, murió al-Ma'mún, el príncipe de Toledo. La sucesión desató amargas luchas entre los partidarios del segundo hijo del príncipe, los partidarios del hijo del difunto príncipe heredero, esto es, el nieto de al-Ma'mún, y un partido republicano que pretendía derrocar a la familia real. En un primer momento, los partidarios del nieto de al-Ma'mún, de nombre al-Qadir, salieron vencedores de esta pugna.
Este al-Qadir no había salido aún de la adolescencia cuando lo instaron a aceptar el papel de príncipe. Fue incapaz de conciliar a los distintos partidos, que seguían luchando, y no digamos ya de someterlos. En marzo del año 1080 el partido republicano formado por los nobles de la ciudad adquirió la supremacía y expulsó de la ciudad a al-Qadir. Éste tuvo que huir tan precipitadamente que dejó atrás a su mujer y su hija. La princesa, hija del señor de Valencia, corrió tras él a pie al menos dos horas, llevando a su hija en brazos, hasta encontrar una mula. El palacio del al-Qasr fue saqueado.
Al-Qadir encontró refugio en la fortaleza de Cuenca. Desde allí se volvió hacia don Alfonso en busca de ayuda y le rindió juramento de vasallaje a cambio de la promesa de que lo repusiera en su trono. Es decir, reconoció oficialmente la sumisión del reino de Toledo a León. Si bien esto aún no abrió a don Alfonso las puertas de las ciudades y castillos de la región, si le permitió moverse libremente por el reino. De la noche a la mañana se había convertido en amo y señor de media península, y había conseguido una vía libre hacia los reinos andaluces del sur.
Otros príncipes andaluces no tardaron en reconocer la nueva posición de don Alfonso. Seis años antes, Abd-Alá de Granada todavía se había dirigido al príncipe de Toledo en busca de ayuda para enfrentarse con Sevilla. Ahora, se volvió del mismo modo hacia el nuevo señor, el rey de León. El rey ingresó en sus arcas el oro andaluz y envió una tropa de refuerzo a Granada. Mucho antes de lo esperado, don Alfonso se había convertido también en un peligro inminente para el reino de Sevilla.
Ibn Ammar sabía que tenía que rechazar como fuese el peligroso ataque granadino, si no quería renunciar a sus planes de unir el sur de Andalucía bajo el gobierno de al-Mutamid. Así, volvió a ponerse en contacto con Zaragoza, y una vez más el hadjib Abú'l-Fadl Hasdai le agenció un ejército de mercenarios. Esta vez no eran tropas de Barcelona, sino un grupo variopinto comandado por un caballero castellano llamado Rodrigo Díaz.
Rodrigo Díaz (que más tarde sería famoso bajo el nombre de «el Cid») era un noble de poca importancia procedente de la región de Burgos. En sus años mozos se había ganado un nombre como duelista, entrando luego al servicio de don Sancho, el rey de Castilla. Tras el asesinato de don Sancho, Rodrigo Díaz había enterrado sus esperanzas de hacer carrera rápidamente. La corte de don Alfonso, en la que los nobles leoneses y franceses eran quienes daban el tono, no ofrecía ninguna perspectiva de futuro a un pequeño señor castellano. Así, Rodrigo Díaz tuvo que buscar otro campo en el que dar rienda suelta a sus ambiciones y su incontenible espíritu emprendedor. Con su propio dinero, reclutó una tropa de aventureros y entró al servicio del príncipe de Zaragoza.