Männen, från 1:a bataljonen The Royal Gurkha Rifles, var i tjänst på tisdagsmorgonen i Nahr-e Saraj, Helmandprovinsen, när afghanerna öppnade eld.
En tros vara en nepalesisk gurkha och de andra två var brittiska medborgare.
Premiärminister David Cameron fördömde morden, men sade att brittiska och afghanska trupper borde samarbeta.
Talibanerna har hävdat att den afghanska soldaten hade gått med i upproret.
En utredning pågår och anhöriga har informerats.
Under tiden, i en separat incident en Royal Marine från 40 Commando dödades i Helmand, sade MoD. Familjen har blivit informerad.
Han sköts ihjäl på tisdag när han var på fotpatrull i Sangin-distriktet.
Antalet brittiska militärer som dödats vid operationer i Afghanistan sedan 2001 uppgår nu till 318.
Cameron sade att den nuvarande strategin att arbeta tillsammans med lokala säkerhetsstyrkor bör fortsätta.
"Det är absolut nödvändigt att vi inte låter denna fruktansvärda händelse förändra vår strategi. Det är det rätta att göra för att bygga upp den afghanska nationella armén, sade han.
Han fortsatte: "Vi måste se till att vi bygger upp den armén eftersom det i slutändan är så vi kommer att kunna få våra trupper tillbaka hem."
På liknande sätt sade försvarsminister Liam Fox: " Att utbilda och utveckla de afghanska nationella säkerhetsstyrkorna är avgörande för det internationella uppdraget i Afghanistan, och dagens händelser kommer inte att undergräva de verkliga framsteg vi fortsätter att göra. Brittiska och Isaf-styrkor arbetar skuldra vid skuldra med afghanerna och kommer att fortsätta att göra det oavskräckt."
Afghanistans president Hamid Karzai har bett Förenade kungariket om ursäkt efter incidenten och en talesman för försvarsministeriet sade att en soldat från Afghanistans nationella armé (ANA) söktes.
Från Jonathan BealeDefence korrespondent, BBC News
Detta är inte första gången denna typ av händelser har hänt.
I november förra året öppnade en medlem av den afghanska nationella polisen eld mot brittiska soldater som han tjänstgjorde vid sidan av. Han dödade fem och skadade ett halvt dussin andra allvarligt.
Men försvarsministeriet är angeläget om att belysa hur sällsynta dessa händelser är.
Sedan 2006 har brittiska styrkor utbildat 130.000 afghanska trupper. Omkring 5 000 av de 10.000 brittiska militärer som för närvarande är utplacerade i Afghanistan arbetar tillsammans med medlemmar av de afghanska säkerhetsstyrkorna dag in och dag ut.
Utbildning och mentorskap av Afghanistans armé och polis är avgörande för målet att så småningom lämna ett Afghanistan som kan ta hand om sin egen säkerhet.
Det är därför Liam Fox betonar att trots denna tragedi kommer brittiska styrkor att "fortsätta att arbeta skuldra vid skuldra med afghanerna" och inte att avskräckas.
Royal Marine dör i Afghanistan
David Cameron talade med president Karzai på tisdagsmorgonen och båda männen var överens om att det krävs en brådskande utredning.
President Karzais talesman Waheed Omar sade att Afghanistans regering också utredde morden och att regeringen skulle "göra allt för att se till att förövarna ställs inför rätta".
BBC förstår att en av soldaterna som dödades sköts och de andra två dödades av en raketdriven granat.
Det finns ett hjälpnummer i Storbritannien för berörda släktingar - 08457 800900.
Talespersonen för Task Force Helmand, överstelöjtnant James Carr-Smith, sade: "Vi tror att detta var handlingar från en ensam individ som har svikit sina Isaf- och afghanska kamrater.
"Hans vistelseort är för närvarande okänd men vi gör stora ansträngningar för att hitta honom. Han bör veta att hans handlingar inte kommer att avskräcka oss från vår uppgift, och vi kommer att fortsätta att arbeta nära våra afghanska vänner för att föra säkerheten till Helmand.
"Tre modiga och hängivna soldater har gjort det ultimata offret. De kommer att saknas och deras handlingar kommer inte att glömmas bort. Vi kommer att minnas dem."
Brittiska soldater i Afghanistan har utbildat 130.000 afghanska trupper sedan 2006, och 5.000 brittiska soldater samarbetar för närvarande med medlemmar av ANA.
Det verkar vara den tredje incidenten där en medlem av de afghanska säkerhetsstyrkorna har öppnat eld mot brittiska trupper.
Reaktion på brittiska soldaters död
Det var en incident 2008 när två brittiska soldater sköts i benet, och en annan i november 2009 när fem brittiska soldater sköts ihjäl av en afghansk polis.
Säkerhetskorrespondenten Frank Gardner sade att han inte var förvånad över att attacken hade inträffat eftersom granskningsprocessen för att ansluta sig till den afghanska militären är dålig. Det är inte ett populärt karriärsteg, sade han, eftersom det är dåligt betalt och farligt.
"Det är viktigt att hålla ett öppet sinne om vad som har motiverat denna person," sade vår korrespondent.
"Denna typ av saker har ofta mer under ytan. Det finns ofta stamfejder, det finns familjefejder; det finns personliga skäl. Så det beror inte alltid på upproret."
Vår korrespondent tillade att tragedin sannolikt skulle intensifiera debatten om de mänskliga kostnaderna för uppdraget i Afghanistan, men han sade att västvärldens exitstrategi bygger på utbildning av de afghanska säkerhetsstyrkorna.
Natobefälhavaren i Afghanistan, general David Petraeus, sade: "Detta är ett gemensamt uppdrag - afghanska trupper och allianstrupper som kämpar skuldra vid skuldra mot talibanerna och andra extremister.
"Vi har offrat mycket tillsammans och vi måste se till att förtroendet mellan våra styrkor förblir stabilt för att besegra våra gemensamma fiender."
Och överste Richard Kemp, en före detta befälhavare för brittiska trupper i Afghanistan, sade till BBC att det var viktigt att komma ihåg att detta var en isolerad händelse och "inte ett mönster av händelser".
Tre brittiska soldater har dödats och fyra skadades av en avfällig afghansk soldat i Afghanistan, sade försvarsministeriet.