Chef Muktar Otieno greps tidigt på torsdagsmorgonen på vägen till Mandera, nära gränsen mellan Kenya och Somalia.
Biträdande chef Abdinoor Dakane berättade för BBC att Mr Otieno var bunden vid ett träd och sköts död av militanterna, efter att lokalbefolkningen misslyckades med att betala en lösensumma.
Al-Shabab har iscensatt en rad attacker i Kenya under de senaste åren.
Kenyanska trupper är en del av Afrikanska unionens uppdrag att bekämpa de islamistiska militanterna i Somalia.
Al-Shabab har ännu inte kommenterat Otienos död.
Hur Garissa har förändrat Kenya
Kenya brister driver al-Shabab rekrytering
Vilka är Somalias al-Shabab?
Under tiden har Kenya förlängt amnesti för al-Shabab-militanter att överlämna sig med ytterligare 14 dagar.
När inrikesminister Joseph Nkaissery gjorde tillkännagivandet, sade några människor redan hade utnyttjat amnesti men vägrade att säga hur många.
Mr Otieno blev bortförd 10 kilometer från den plats där al-Shabab-kanoner dödade 28 personer som åkte buss i Mandera i november förra året.
Enligt biträdande chef, som bevittnade mr Otienos bortförande, lyckades en grupp lokala äldste spåra upp angriparna till en stad vid gränsen mellan Kenya och Somalia.
Gruppen vädjade till militanterna att frige hövdingen, men när de inte betalade en lösensumma på 4 miljoner kenyanska shilling (42.000 dollar; 28.000 pund) sköts Otieno ihjäl inför de äldste i klanen, berättade han för BBC:s somaliska tjänst.
Mr Dakane berättade för BBC att han nu avgick från sin tjänst som biträdande chef för Arabia avdelningen eftersom han fruktade för sitt liv.
Det har ännu inte kommit några officiella kommentarer från de kenyanska myndigheterna.
Mordet kommer i en tid av ökad spänning över säkerheten i Kenya, efter islamistiska al-Shabab fighters dödade 148 personer, främst studenter, under en attack på ett universitet i Garissa tidigare denna månad.
Misstänkta al-Shabab militanter har kidnappat och dödat en traditionell hövding i norra Kenya, säger en lokal äldste.