diff --git a/MdePkg/Library/BasePeCoffLib/BasePeCoff.c b/MdePkg/Library/BasePeCoffLib/BasePeCoff.c
index 28c84062d125..23cb691ad729 100644
--- a/MdePkg/Library/BasePeCoffLib/BasePeCoff.c
+++ b/MdePkg/Library/BasePeCoffLib/BasePeCoff.c
@@ -1106,17 +1106,20 @@ PeCoffLoaderRelocateImage (
           Fixup32   = (UINT32 *) (Fixup16 - 1);
           *Fixup16  = (UINT16) ((*Fixup32 + (UINT32) Adjust) >> 16);
           if (FixupData != NULL) {
-            *(UINT16 *) FixupData = *Fixup16;
-            FixupData             = FixupData + sizeof (UINT16);
+            FixupData             = ALIGN_POINTER (FixupData, sizeof (UINT32));
+            *(UINT32 *) FixupData = *Fixup32 + (UINT32) Adjust;
+            FixupData             = FixupData + sizeof (UINT32);
           }
           break;
 
         case EFI_IMAGE_REL_BASED_LOW:
           Fixup16   = (UINT16 *) Fixup;
-          *Fixup16  = (UINT16) (*Fixup16 + (UINT16) Adjust);
+          Fixup32   = (UINT32 *) Fixup16;
+          *Fixup16  = (UINT16) ((*Fixup32 + (UINT32) Adjust) & 0xffff);
           if (FixupData != NULL) {
-            *(UINT16 *) FixupData = *Fixup16;
-            FixupData             = FixupData + sizeof (UINT16);
+            FixupData             = ALIGN_POINTER (FixupData, sizeof (UINT32));
+            *(UINT32 *) FixupData = *Fixup32 + (UINT32) Adjust;
+            FixupData             = FixupData + sizeof (UINT32);
           }
           break;
 
@@ -1725,6 +1728,8 @@ PeCoffLoaderRelocateImageForRuntime (
   UINTN                               Adjust;
   RETURN_STATUS                       Status;
   UINT16                              Magic;
+  UINT8                               HighLowMask [SIZE_4KB / (8 * sizeof(UINT32))];
+  UINTN                               HighLowMaskIndex;
 
   OldBase = (CHAR8 *)((UINTN)ImageBase);
   NewBase = (CHAR8 *)((UINTN)VirtImageBase);
@@ -1816,6 +1821,8 @@ PeCoffLoaderRelocateImageForRuntime (
     RelocEnd  = (UINT16 *) ((UINT8 *) RelocBase + RelocBase->SizeOfBlock);
     FixupBase = (CHAR8 *) ((UINTN)ImageBase) + RelocBase->VirtualAddress;
 
+    ZeroMem (HighLowMask, sizeof (HighLowMask));
+
     //
     // Run this relocation record
     //
@@ -1830,20 +1837,42 @@ PeCoffLoaderRelocateImageForRuntime (
       case EFI_IMAGE_REL_BASED_HIGH:
         Fixup16 = (UINT16 *) Fixup;
         Fixup32 = (UINT32 *) (Fixup16 - 1);
-        if (*(UINT16 *) FixupData == *Fixup16) {
+        HighLowMaskIndex = ((UINTN) Fixup32 & SIZE_4KB) >> 2;
+        FixupData = ALIGN_POINTER (FixupData, sizeof (UINT32));
+        if (*(UINT32 *) FixupData == *Fixup32 ||
+            (HighLowMask [HighLowMaskIndex >> 3] & (1 << (HighLowMaskIndex & 7))) != 0) {
+
           *Fixup16 = (UINT16) ((*Fixup32 + (UINT32) Adjust) >> 16);
+
+          //
+          // Mark this location in the page as requiring the low relocation to
+          // be reapplied as well. This is necessary since the *Fixup comparison
+          // with its FixupData will fail now that we have updated the high word.
+          //
+          HighLowMask [HighLowMaskIndex >> 3] |= (1 << (HighLowMaskIndex & 7));
         }
 
-        FixupData = FixupData + sizeof (UINT16);
+        FixupData = FixupData + sizeof (UINT32);
         break;
 
       case EFI_IMAGE_REL_BASED_LOW:
         Fixup16 = (UINT16 *) Fixup;
-        if (*(UINT16 *) FixupData == *Fixup16) {
+        HighLowMaskIndex = ((UINTN) Fixup16 & SIZE_4KB) >> 2;
+        FixupData = ALIGN_POINTER (FixupData, sizeof (UINT32));
+        if (*(UINT32 *) FixupData == *(UINT32 *)Fixup ||
+            (HighLowMask [HighLowMaskIndex >> 3] & (1 << (HighLowMaskIndex & 7))) != 0) {
+
           *Fixup16 = (UINT16) (*Fixup16 + ((UINT16) Adjust & 0xffff));
+
+          //
+          // Mark this location in the page as requiring the high relocation to
+          // be reapplied as well. This is necessary since the *Fixup comparison
+          // with its FixupData will fail now that we have updated the low word.
+          //
+          HighLowMask [HighLowMaskIndex >> 3] |= (1 << (HighLowMaskIndex & 7));
         }
 
-        FixupData = FixupData + sizeof (UINT16);
+        FixupData = FixupData + sizeof (UINT32);
         break;
 
       case EFI_IMAGE_REL_BASED_HIGHLOW:
