diff --git a/IPython/core/interactiveshell.py b/IPython/core/interactiveshell.py
index 21e428b..e137c92 100644
--- a/IPython/core/interactiveshell.py
+++ b/IPython/core/interactiveshell.py
@@ -3138,8 +3138,12 @@ class InteractiveShell(SingletonConfigurable):
             else:
                 cell = raw_cell
 
+        # Do NOT store paste/cpaste magic history
+        if "get_ipython().run_line_magic(" in cell and "paste" in cell:
+            store_history = False
+
         # Store raw and processed history
-        if store_history and raw_cell.strip(" %") != "paste":
+        if store_history:
             self.history_manager.store_inputs(self.execution_count, cell, raw_cell)
         if not silent:
             self.logger.log(cell, raw_cell)
diff --git a/IPython/terminal/magics.py b/IPython/terminal/magics.py
index 66d5325..cea53e4 100644
--- a/IPython/terminal/magics.py
+++ b/IPython/terminal/magics.py
@@ -147,7 +147,7 @@ class TerminalMagics(Magics):
 
         sentinel = opts.get('s', u'--')
         block = '\n'.join(get_pasted_lines(sentinel, quiet=quiet))
-        self.store_or_execute(block, name, store_history=False)
+        self.store_or_execute(block, name, store_history=True)
 
     @line_magic
     def paste(self, parameter_s=''):