しんのすけたちは幼稚園の春の遠足で、新しくできたテーマパーク“群馬ヘンダーランド”へ出掛けた。ふとした拍子にみんなとはぐれたしんのすけは、サーカス小屋のテントに迷い込み、そこで檻に入れられた可愛い女の子を見つける。彼女はメモリ・ミモリという異次元王国ヘンダーランドの王女で、オカマ魔女のマカオとジョマによって閉じ込められてしまったのだった。王女を助けようとしたしんのすけだったが、オカマ魔女の手下クレイ・Ｇ・マッドとチョキリーヌ・ベスタの妨害にあい、人形のトッペマ・マペットの助けを借りてその場から逃げ帰るのが精一杯だった。トッペマは魔女の魔法のトランプをしんのすけに託し、ヘンダーランドを救ってほしいと助けを求める。しんのすけは恐怖に尻込みしていたが、トランプを取り返すために現れた雪だるまのス・ノーマン・パーにひろしとみさえを連れ去られてしまい、「オラ、父ちゃん母ちゃんをお助けに行くゾ！」と奮い立ち、トランプを片手にヘンダーランドへ向かった。しんのすけは真っ先に襲ってきたクレイ・Ｇをトッペマと協力して破り、Ｔシャツに姿を変えられていたひろしを助け出す。ヘンダー城へ向かったしんのすけたちはチョキリーヌの襲撃を受けるが、トッペマが自分の身を犠牲にしてこれを倒し、やはりブラジャーに変えられていたみさえが元の姿で帰ってきた。いよいよ城へ乗り込んだしんのすけたちは、トランプの魔法の力でオカマ魔女を倒し、ヘンダーランドにかけられた封印を解くのだった。平和が戻ったヘンダー王国では、助け出されたメモリ姫がゴーマン王子と幸せを取り戻していた。