diff --git a/bolt/include/bolt/Core/BinarySection.h b/bolt/include/bolt/Core/BinarySection.h
--- a/bolt/include/bolt/Core/BinarySection.h
+++ b/bolt/include/bolt/Core/BinarySection.h
@@ -43,6 +43,9 @@
 class BinarySection {
   friend class BinaryContext;
 
+  /// Count the number of sections created.
+  static uint64_t Count;
+
   BinaryContext &BC;           // Owning BinaryContext
   std::string Name;            // Section name
   const SectionRef Section;    // SectionRef (may be null)
@@ -86,6 +89,7 @@
   uint64_t OutputSize{0};          // Section size in the rewritten binary.
   uint64_t OutputFileOffset{0};    // File offset in the rewritten binary file.
   StringRef OutputContents;        // Rewritten section contents.
+  const uint64_t SectionNumber;    // Order in which the section was created.
   unsigned SectionID{-1u};         // Unique ID used for address mapping.
                                    // Set by ExecutableFileMemoryManager.
   uint32_t Index{0};               // Section index in the output file.
@@ -147,13 +151,14 @@
         Size(Section.getSize()), Alignment(Section.getAlignment()),
         ELFType(Section.getELFType()), ELFFlags(Section.getELFFlags()),
         Relocations(Section.Relocations),
-        PendingRelocations(Section.PendingRelocations), OutputName(Name) {}
+        PendingRelocations(Section.PendingRelocations), OutputName(Name),
+        SectionNumber(++Count) {}
 
   BinarySection(BinaryContext &BC, SectionRef Section)
       : BC(BC), Name(getName(Section)), Section(Section),
         Contents(getContents(Section)), Address(Section.getAddress()),
         Size(Section.getSize()), Alignment(Section.getAlignment()),
-        OutputName(Name) {
+        OutputName(Name), SectionNumber(++Count) {
     if (isELF()) {
       ELFType = ELFSectionRef(Section).getType();
       ELFFlags = ELFSectionRef(Section).getFlags();
@@ -173,7 +178,7 @@
         Contents(reinterpret_cast<const char *>(Data), Data ? Size : 0),
         Address(0), Size(Size), Alignment(Alignment), ELFType(ELFType),
         ELFFlags(ELFFlags), IsFinalized(true), OutputName(Name),
-        OutputSize(Size), OutputContents(Contents) {
+        OutputSize(Size), OutputContents(Contents), SectionNumber(++Count) {
     assert(Alignment > 0 && "section alignment must be > 0");
   }
 
@@ -207,10 +212,34 @@
 
   // Order sections by their immutable properties.
   bool operator<(const BinarySection &Other) const {
-    return (getAddress() < Other.getAddress() ||
-            (getAddress() == Other.getAddress() &&
-             (getSize() < Other.getSize() ||
-              (getSize() == Other.getSize() && getName() < Other.getName()))));
+    // Allocatable before non-allocatable.
+    if (isAllocatable() != Other.isAllocatable())
+      return isAllocatable() > Other.isAllocatable();
+
+    // Input sections take precedence.
+    if (hasSectionRef() != Other.hasSectionRef())
+      return hasSectionRef() > Other.hasSectionRef();
+
+    // Compare allocatable input sections by their address.
+    if (getAddress() != Other.getAddress())
+      return getAddress() < Other.getAddress();
+    if (getAddress() && getSize() != Other.getSize())
+      return getSize() < Other.getSize();
+
+    // Code before data.
+    if (isText() != Other.isText())
+      return isText() > Other.isText();
+
+    // Read-only before writable.
+    if (isReadOnly() != Other.isReadOnly())
+      return isReadOnly() > Other.isReadOnly();
+
+    // BSS at the end.
+    if (isBSS() != Other.isBSS())
+      return isBSS() < Other.isBSS();
+
+    // Otherwise, preserve the order of creation.
+    return SectionNumber < Other.SectionNumber;
   }
 
   ///
@@ -228,13 +257,13 @@
   bool isText() const {
     if (isELF())
       return (ELFFlags & ELF::SHF_EXECINSTR);
-    return getSectionRef().isText();
+    return hasSectionRef() && getSectionRef().isText();
   }
   bool isData() const {
     if (isELF())
       return (ELFType == ELF::SHT_PROGBITS &&
               (ELFFlags & (ELF::SHF_ALLOC | ELF::SHF_WRITE)));
-    return getSectionRef().isData();
+    return hasSectionRef() && getSectionRef().isData();
   }
   bool isBSS() const {
     return (ELFType == ELF::SHT_NOBITS &&
diff --git a/bolt/lib/Core/BinarySection.cpp b/bolt/lib/Core/BinarySection.cpp
--- a/bolt/lib/Core/BinarySection.cpp
+++ b/bolt/lib/Core/BinarySection.cpp
@@ -26,6 +26,8 @@
 extern cl::opt<bool> HotData;
 } // namespace opts
 
+uint64_t BinarySection::Count = 0;
+
 bool BinarySection::isELF() const { return BC.isELF(); }
 
 bool BinarySection::isMachO() const { return BC.isMachO(); }
diff --git a/bolt/test/runtime/X86/section-order.test b/bolt/test/runtime/X86/section-order.test
new file mode 100644
--- /dev/null
+++ b/bolt/test/runtime/X86/section-order.test
@@ -0,0 +1,12 @@
+REQUIRES: system-linux
+
+RUN: %clang %p/Inputs/basic-instrumentation.s -Wl,-q -o %t.exe
+RUN: llvm-bolt %t.exe -o %t --instrument
+RUN: llvm-readelf --section-headers %t | FileCheck %s
+
+## Verify that llvm-bolt outputs new sections in expected order.
+CHECK: .text.bolt.extra.1
+CHECK: .rodata.bolt.extra.1
+CHECK: .data.bolt.extra.1
+CHECK: .bss.bolt.extra.1
+