Հիմնվելով Հիքայաթ Մերոնգ Մահավանգսայում (նաև հայտնի է որպես Կեդահի տարեգրություն) տրված հաշվետվության վրա, Կեդայի սուլթանությունը ձևավորվել է, երբ թագավոր Ֆրա Օնգ Մահավանգսան ընդունել է իսլամ և ընդունել Սուլթան Մուդզաֆար Շահ անունը:Աթ-Թարիխ Սալասիլա Նեգերի Քեդահը նկարագրել է իսլամական հավատքի ընդունումը սկսված մ.թ. 1136թ.-ից:Այնուամենայնիվ, պատմաբան Ռիչարդ Ուինսթեդը, մեջբերելով աքեհենական պատմությունը, նշել է 1474 թվականը Կեդայի տիրակալի կողմից իսլամ ընդունելու տարվա համար։Այս ավելի ուշ ամսաթիվը համընկնում է Մալայական տարեգրության մեջ, որտեղ նկարագրվում է Քեդայի ռաջան, որն այցելում էր Մալաքկա իր վերջին սուլթանի օրոք՝ փնտրելով թագավորական խմբի պատիվը, որը նշում է մալայական մահմեդական տիրակալի ինքնիշխանությունը:Կեդահի խնդրանքը պատասխան էր Մալակկայի վասալ լինելուն, հավանաբար, կապված Այութայան ագրեսիայի վախի հետ:[ ^{[76] []} Առաջին բրիտանական նավը Կեդահ ժամանեց 1592 թվականին։Նա դրան հասավ՝ հավաստիացնելով սուլթան Մուհամմադ Ջիվա Զայնալ Ադիլին II-ին, որ իր բանակը կպաշտպանի Քեդային ցանկացած սիամական ներխուժումից:Դրա դիմաց սուլթանը համաձայնեց Պենանգը հանձնել բրիտանացիներին։