Es posible que ya entonces Álvaro de Luna comenzase a plantear la nueva fortaleza de Cuéllar, pero dispuso de escaso tiempo material para llevarlas a cabo: en 1439 fue desterrado de la corte, y el señorío de la villa fue cedido por Juan II de Castilla el 26 de abril del mismo año a su homónimo el rey de Navarra, quien lo poseyó hasta 1444.