接下来两年的书记处工作，大部分是组织工作，这是在1956年9月中共第八次全国代表大会上批准的一个职能完全不同的更具有政治色彩的秘书处。邓在“八大”被选为中共中央总书记（与邓在1954和1955年担任的中央委员会秘书长相比，该职位的权力更大）。邓受命担负起了修改党章的重任，这是他在这次代表大会上所带来的许多主要变化之一。正如他在讲话中所阐述的那样：自从1945年上次大会以来，党的状况已经发生了相当大的变化，我们党已夺取了全国政权，成了执政党；党员从一百多万增加到一千一百万，以前这些党员大部分是在解放区的农村里，现我们的党员分布到全国的每一个城镇；党的目标已经从夺取全国政权转变为发展国民经济。为了适应这种变化了的政治环境，邓建议进行一次全面彻底的总结，把所有经验都要适当反映到新的党章中。
1953年12月高、饶阴谋的破产，使党特别重视了党的团结，规定了反对破坏团结的若干具体办法，但这些并不能马上邓得成功。1954年早些时候，中共中央委员会全体会议没有轻易地得到高和饶的完全坦白。后来，邓小平通过他的中共中央秘书长的新职务，在调查高、饶问题的工作中对彻底弄清他们的错误发挥了重要作用。在1955年3月召开的中共全国代表大会上才提交了关于高、饶反党联盟的最后报告。在高、饶事件中，林彪没有失宠。所以没有引起人们的注意。为了满足支持高岗的那些人所提的论调，林彪和邓小平都进入了政治局，因为他俩都被认作是1949年前军队利益的代表人物。另外，邓成了中共组织部长、国防委员会副主席。然而，邓在中共的领导层内作为政界与军界之间的纽带作用并没有就此结束。当1955年9月为承认那些年军队在战争中作出的贡献，人民解放军首次为将军们授衔时，中共中央军事委员会任命邓作为这次授衔的最后仲裁者。人民解放军总政治部对军衔作了暂时性的分配。
“文化大革命”期间的一些资料特别是各种“红卫兵”组织撰写和分发的资料，尖锐地批判了邓小平建议把涉及毛泽东思想的字样从党章中删掉的行为，他们把这看作是反对毛和迎合苏联论调的主要依据。那时邓刚从莫斯科（4月）回来，在那儿他参加了苏共第二十次代表大会，听了赫鲁晓夫对个人崇拜的谴责。一些西方评论家如D·W常和鲍纳维亚，曾由于相类似的原因而把邓与毛关系的破裂追溯到这个时期。
他在中共“八大”关于修改党章的重要讲话中，以一定的篇幅阐述了在党内进行辩论的正确程序、集体领导的必要性和民主集中制的重要性。根据邓的观点，如果想找到正确处理问题的方法，在党内进行公开辩论是必要的。在辩论中，个人应畅所欲言，少数人的意见即使是错误的也应当受到尊重，党内斗争不应采取“过火斗争和惩办主义”的政策（邓自己在1933年曾经历过的所谓“残酷斗争”和“无情打击”）。另一方面，对待错误也不应听之任之过分迁就。但是，党的决定一经做出，每个党员有义务必须贯彻执行。批评和集体领导是党内民主最基本的保证。没有批评，每个党员包括领导干部在内就不可能改进他们的工作作风，提高他们的思想认识；没有集体领导，政治将会变成个人崇拜。党章必须公平地适用于每一个党员，不应该有“个人崇拜”。领导干部相互之间或在对待下属的问题上不应滥用职权。
“看见那个小个子了吗？他非常聪明而且前途远大。”邓的屡次提升，使他置于中共组织画务的核心位置，组织工作就成为邓这十年的后几年所要做的主要工作。当时被任命的中央委员会秘书处的其他成员有刘澜涛、宋任穷、谭震林和杨尚昆。它的组成清楚地表明中共所强调的团结，因为这些人都代表着党内各方面的成分：刘澜涛是陕北苏维埃时高岗的同事，尽管从1933年以来他们有过多次冲突，最显著的是1938—1941年期间在太行山区的杨尚昆经邓的周旋，使他和秘书处的大部分人保持了极好的政治关系。宋任穷曾是八路军一二九师政训处副主任。谭震林和邓小平一样，自从三十年代就和毛泽东开始了共事。刘澜涛是薄一波的追随者，在太行山区是邓的同事，是1953年受高岗攻击的主要受害者。
毛和邓的关系似乎又一次成为中共政治的主要关系。邓能够使党的团结和战斗力得到保证。1954年后半年赫鲁晓夫访问了北京，1958年又来一次。在1957年赫在莫斯科招待了毛率领的中共代表团，邓也是代表团成员，赫对此有一种有趣的回忆：他不喜欢毛的主要原因是毛从来不说他的党内同事的好话。赫说：“毛从来不承认他的同事与他平等。毛唯一似乎满意的一位同志是邓小平，我记得毛指着邓小平对我说：
除了高岗和饶漱石，邓没有点其他人的名，不过他的批评很尖锐。他说：“有少数党组织的负责人，仍然有个人包办行为”；“对于领袖的爱护—本质上是表现对于党的利益、阶级的利益和人民的利益的爱护，而不是对个人的神化”；和“至今还有不少党组织的负责人……并没有采取鼓励和支持由下而上的批评态度，有一部分人甚至对于批评者采取可耻的打击报复的办法”。
有趣的是，邓在当时的许多建议不仅预言了他在八十年代初将要开始实行的政治改革计划，而且也是他四十年代初在太行山区已经形成的理论与实践的继续。一个例子就是党政职能清楚地分开，以便加强党的领导。游击战期间，中共必需参与所有的活动，这是它的优势。但在五十年代初，中央领导经常批评党过多地插手和管理政府工作的倾向，以致使政府部门只会等靠党的指示办事，加重了党的负担，造成了党的系统的混乱现象。1941年邓曾在中共北方局一次会议上发言中概括地提出类似这些问题的解决办法，这些办法曾在太行山区实行过，后来在中共北方机关刊物《党的生活》上发表了一篇题为《党与抗日民主政权》的文章。
邓不仅关心行政事务，他在这次代表大会上所作的报告以相当长的篇幅论述了党的程序和准则。他曾强调：特别是在赢得大众支持和保持党的团结方面，要把1935年之后的党的传统作为行动指南。这就是党章中最显著后来又完全被人误解的变化之一的基本的来龙去脉。1945年的中共党章明确规定马列主义毛泽东思想是党的指导思想，但在1956年的党章中将“毛泽东思想”删掉了，仅留下“马列主义”作为中国共产党的指导思想。
以苏联为榜样跟着苏联路子走，不可能是党内变化的主要原因，因为1953年共青团的章程已把涉及毛泽东思想的字样删掉了。由于意识形态方面措词的变化具有极其重要的象征意义，因此这个决定不是由中共领导层集体决定的说法简直令人不可思议。尽管他在中共“八大”的讲话中批评了个人崇拜，但他强调与苏共不一样，中共总是认为任何个人和任何政党错误总是难免的，因此我们从来不愿采取苏共那样全盘否定的作法。而且，这时，实际上是在这前后的很多年中，他主要的工作就是维护党的纪律和党的团结。在那种特定的情况下，邓不无道理地担忧，当时毛泽东思想的地位正在导致中国政治中越来越严重的个人崇拜，这种个人崇拜不仅对毛泽东本人的领导，而且对党组织的领导都会造成威胁。尽管他不同意毛有关中国未来的一些观点，但他还是相信只要不威胁到党的团结，只要决策是由集体来做，意见不一致是正常的、合理的也是欢迎的。事实上，邓完全懂得毛在中共政治中独一无二的作用，但他仍然把党的集体领导看作是一大优势，因此，他希望继续对毛泽东思想进行宣传，即使这个用语已正式从党章中撤了下来。
肯定在后来，这些讲话可能被解释为是针对毛的。在1955年进行的关于集体化的讨论导致了“农业合作化的高潮”。正是这次讨论急剧地改变了中国政策的方向。后来这次讨论常常受到人们强烈的指责。与政府》1993年第26卷第3、4章。">人们过去认为，毛主席背过中央的其他领导，通过向省一级的领导呼吁新掀起的农业合作化的高潮，是由于当时中央做出了一些他所不喜欢的决策。尽管关于农业合作化高潮来由的解释现在看来似乎有点走极端，但从1955年后半年起他在政策的形成过程中越来越多地领先省一级的领导人，从而迫使中央的领导同意1956年初的发展速度和“全国十二年农业发展纲要”发展的速度。然而，在后来的一些年里，最能表现毛特征的那些行为和邓曾在谈话中所预言过的那种情况还没有完全出现。同样，当时有一些人觉得没有按党的准则去做而感到内疚，他们也是邓批评的对象。
